package main.java.algorithms;

import main.java.utils.SortTestHelper;

import java.util.Random;

/**
 * @author Wrb
 * @date 2019/5/27 18:02
 */
public class QuickSort2 implements Sort {
	@Override
	public void sort(int[] arr, int n) {
		sort(arr, 0, n - 1);
	}

	//递归进行快排
	private void sort(int[] arr, int l, int r) {

		//优化1 当数组小到一定程度，插入排序比归并排序快，此时调用插入排序
		if (r - l <= 20) {
			InsertionSort.sort(arr, l, r);
			return;
		}

		int p = partition2(arr, l, r);
		sort(arr, l, p - 1);
		sort(arr, p + 1, r);
	}

	//优化3 在有大量重复键值的时候效率更高
	//对数组arr[l....r]部分进行partition操作
	//从arr[l...r]两边往里查找
	private int partition2(int[] arr, int l, int r) {
		//优化2：随机选取基准
		SortTestHelper.swap(arr, l, new Random().nextInt(r - l + 1) + l);
		int v = arr[l];

		//arr[l+1...i]<=v , arr[j...r]>=v
		int i = l + 1, j = r;
		while (true){
			while (i <= r && arr[i] < v) {
				i++;
			}
			while (j >= l + 1 && arr[j] > v) {
				j--;
			}
			if (i > j) {
				break;
			}
			SortTestHelper.swap(arr, j, i);
			i++;
			j--;
		}
		SortTestHelper.swap(arr, l, j);
		return j;
	}
}
